//哈希表
#ifndef __HASHTABLE__HPP
#define __HASHTABLE__HPP

#include"../Universal.h"

namespace NgSiuKei {

template<class TheClass>
struct hash_table_node {
    U_L_L key;
    TheClass val;
    hash_table_node<TheClass> *next;
};
#define ht_node hash_table_node

template<class TheClass>
class HashTable {
    public:
    HashTable(void);
    ~HashTable(void);

    public:
    void clear(void);
    TheClass getVal(const U_L_L &key) const;
    void setVal(const U_L_L &key, const TheClass &val);
    void deleteVal(const U_L_L &key);
    void print(void);

    private:
    U_L_L hash(const U_L_L& key) const;//哈希函数

    private:
    ht_node<TheClass> *p;
};

template<class TheClass>
HashTable<TheClass>::HashTable(void) {
    this->p = new ht_node<TheClass>[MAX_SIZE];
    for(U_L_L i=0; i<MAX_SIZE; ++i) {
        (this->p[i]).next = nullptr;//数组内每一个链表头节点都只有标记链表地址的作用
    }
}

template<class TheClass>
HashTable<TheClass>::~HashTable(void) {
    this->clear();
    delete this->p;
}

template<class TheClass>
void HashTable<TheClass>::clear(void) {
    ht_node<TheClass> *currentNode = nullptr;
    ht_node<TheClass> *deleteNode = nullptr;
    for(U_L_L i=0; i<MAX_SIZE; ++i) {
        currentNode = (this->p[i]).next;
        while(nullptr != currentNode) {
            deleteNode = currentNode;
            currentNode = currentNode->next;
            delete deleteNode;
        }
        (this->p[i]).next = nullptr;
    }
}

template<class TheClass>
TheClass HashTable<TheClass>::getVal(const U_L_L &key) const{
    U_L_L index = this->hash(key);
    if(nullptr == (this->p[index]).next) {
        throw EXCEPTION_CAN_NOT_FIND;
    }

    ht_node<TheClass> *currentNode = (this->p[index]).next;
    while(nullptr != currentNode) {
        if(key == currentNode->key) {
            return currentNode->val;
        }
        currentNode = currentNode->next;
    }
    throw EXCEPTION_CAN_NOT_FIND;
}

template<class TheClass>
void HashTable<TheClass>::setVal(const U_L_L &key, const TheClass &val) {
    U_L_L index = this->hash(key);

    //生成新节点
    ht_node<TheClass> *newNode = new ht_node<TheClass>;
    newNode->key = key;
    newNode->val = val;
    newNode->next = nullptr;
    
    if(nullptr == (this->p[index]).next) {
        (this->p[index]).next = newNode;
    }
    else {
        ht_node<TheClass> *currentNode = this->p+index;
        //移动到对应key节点的前一个节点，或链表最后一个节点
        while(nullptr != currentNode->next && key != currentNode->next->key) {
            currentNode = currentNode->next;
        }

        if(nullptr == currentNode->next) {
            //链表尾新加节点
            currentNode->next = newNode;
        }
        else {
            currentNode->next->val = val;
            //因为不需要用到newNode，所以要释放空间
            delete newNode;
        }
    }
}

template<class TheClass>
void HashTable<TheClass>::deleteVal(const U_L_L &key) {
    U_L_L index = this->hash(key);
    if(nullptr == (this->p[index]).next) {
        return;
    }
    else {
        ht_node<TheClass> *currentNode = &(this->p[index]);
        //移动到对应key节点的前一个节点，或链表最后一个节点
        while(nullptr != currentNode->next && key != currentNode->next->key) {
            currentNode = currentNode->next;
        }

        if(nullptr == currentNode->next) {
            return;
        }
        else {
            ht_node<TheClass> *deleteNode = currentNode->next;
            
            //删除
            currentNode->next = deleteNode->next;

            //释放待删除节点空间
            delete deleteNode;
        }
    }
}

template<class TheClass>
void HashTable<TheClass>::print(void) {
    cout << "打印哈希表：" << endl;
    for(U_L_L i=0; i<MAX_SIZE; ++i) {
        cout << "[" << i << "] ";
        ht_node<TheClass> *currentNode = (this->p[i]).next;
        while(nullptr != currentNode) {
            cout << "-> (k=" << currentNode->key << "|v=" << currentNode->val << ") ";
            currentNode = currentNode->next;
        }
        cout << endl;
    }
    cout << endl;
}

template<class TheClass>
U_L_L HashTable<TheClass>::hash(const U_L_L& key) const {
    return key%MAX_SIZE;

    //理论上来说key不会只支持一种类型，但我每心思搞这个了，有机会再弄吧
    U_L_L i = 0;
    U_L_L num = 0;
    if(key > 0) {
        i=1;
        U_L_L k = key;
        while(k > 0) {
            if(k&1) {
                num += i;
            }
            k >>= 1;
            i++;
        }
    }
    num = (num%MAX_SIZE)*(num%MAX_SIZE);
    return num%MAX_SIZE;
}

}

#endif